package com.example.lcode.binary;

import java.util.PriorityQueue;

public class Question378 {

    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((o1, o2) -> {
            return o1[0] - o2[0];
        });
        for (int i = 0; i < matrix.length; i++) {
            priorityQueue.offer(new int[]{matrix[i][0], i, 0});
        }
        for (int i = 0; i < k - 1; i++) {
            int[] poll = priorityQueue.poll();
            if (poll[2] != matrix[0].length - 1) {
                int y = poll[1];
                int x = poll[2] + 1;
                priorityQueue.offer(new int[]{matrix[y][x], y, x});
            }
        }
        return priorityQueue.poll()[0];
    }

    public static void main(String[] args) {

    }

}
